
\documentclass[a4paper,10pt]{article}
\usepackage{color}
% \usepackage{fancyhdr}
\usepackage[utf8]{inputenc}

\usepackage{enumerate}
\usepackage{latexsym}
\usepackage{amssymb}
\usepackage{ulem}
% \usepackage{ifsym}
\usepackage{graphicx}
%\usepackage[margin=3cm]{geometry}

%\renewcommand{\headheight}{16pt}

%\newcommand{\HRule}{\rule{\linewidth}{0.1mm}}

\begin{document}

%\begin{titlepage}
\begin{center}
	\textsc{\Large Distributed Database Systems (WS 11/12) }\\[0.3cm]
	\textsc{\large Assignment 10}\\[1cm]
        Adam Grycner\\
        Szymon Matejczyk\\
        Guo Xinyi\\
        Yu Chenying\\[1cm]
        \today\\[1cm]
        \rule{\linewidth}{0.1mm}\\
 	%\HRule\\
%	\HRule\\[2cm]
	
\end{center}
\section{Exercise 10.1: Discussion}
\begin{enumerate}[1.]
  \item
    Semantic web is similar to web 2.0 we know. It consists also of sites serving different types of content. However, the content is in a format readable for machines, what makes it easier(and therefore practically possible) to exchange data and query different sites at the same time.
  \item
    Lookup-based query processing is good, when the data we are searching is not often updated. In this case indexes made by crawlers become easily outdated. Federated processing in hard, because different sites use different querying language.
  \item Optimizations in distributed RDF processing
    \begin{itemize}
      \item Using crawlers to cache parts of results(meta-data, popular terms), creating indexes
      \item Using statistics to choose a good plan(cost model)
      \item Simpllifying queries
      \item Source selection - querying only sources that may have some results. It's possible to query only specialized sources for specialized data.
    \end{itemize}
\end{enumerate}

\section{Exercise 10.2: Cardinality Estimation}
\begin{enumerate}[ \ a)]
 \item
 \begin{itemize}
   \item card(?, ?, ?) = $| d |$
   \item card(s, ?, ?) = $| d | * sel_{s_d}$
   \item card(?, p, ?) = $card_d(p)$
   \item card(?, ?, o) = $| d | * sel_{o_d}$
   \item card(s, p, ?) = $card_d(p) * sel_{s_d}(p)$
   \item card(s, ?, o) = $| d | * sel_{s_d} * sel_{o_d}$
   \item card(?, p, o) = $card_d(p) * sel_{o_d}(p)$
   \item card(s, p, o) = $card_d(p) * sel_{s_d}(p) * sel_{o_d}(p)$
 \end{itemize}
where\\
 $| d | $ - triples in source\\
 $1/sel_{s_d}$ - distinct subjects in source\\
 $1/sel_{o_d}$ - distinct objects in source\\
 $card_d(p)$ - VoID Predicate Statistics\\
 $1/sel_{s_d}(p)$ - distinct subjects for predicate p\\
 $1/sel_{o_d}(p)$ - distinct objects for predicate p\\

 \item $card( q_1 \Join q_2) = card(q_1) * card(q_2) * sel_{\Join}(q_1,q_2)$
where\\
$1/sel_{\Join}(q_1,q_2)$ - $max\{number\_of\_dif\_values\_on\_join\_attr(q_1),\\  number\_of\_dif\_values\_on\_join\_attr(q_2)\}$
\end{enumerate}

\section{Exercise 10.3: SPARQL SERVICE Operator}
a) Suppose there are n subqueries in a SPARQL query. First, pick out two of the n subqueries to join and get result 1. Then pick out one in the rest n-2 subqueries to join with result 1 and get result 2......Until all the subqueries are joined. Thus we have n! kinds of plans.
\end{document}
